package imooc_math;
//Quick Union
//将两个节点连接在一起：将两个节点的根节点连接在一起
//parent[i]表示i的父亲元素是谁
//9-4时，将9-4的根节点8
//拥有相同的跟：连接在一起的
public class UF2 {
	public int[] parent;
	public int count;
	public UF2(int n){
		count = n;
		parent=new int[n];
		for(int i=0;i<n;i++){
			parent[i] = i;
		}
	}
	//让p跟q所在的组的所有数的id都相同
	public void union(int p,int q){
		int pRoot = find(p);
		int qRoot = find(q);
		if(pRoot == qRoot){
			return;
		}
		parent[pRoot] = qRoot;		
	}
	//Quick find 时间复杂度：O(n)
	public int find(int p){
		while(parent[p] != p){
			p = parent[p];
		}
		return p;
	}
	public boolean isConnected(int p,int q){
		return find(p) == find(q);
	}


}
